# homework 寻找某个点周围距离最近的k个点

#2<=x<=4 1<=y<=4 给定点m=(3,3)

#point = (x,y)

point_m = (3,3)

distance_list=[]
for x in range(2,5):
    for y in range(1,5):
        point_i = (x,y)

        distance = (((x-3)**2) + ((y-3)**2))**0.5
        distance_list.append({'point':point_i,'distance':round(distance,2)})

def get_distance(dict):
    return dict['distance']

distance_list.sort(key=get_distance,reverse=True)
print(distance_list)

#假设我们只找4个点

for i in range(4):
    print('距离最近的第{}个点：{}，距离是{}'.format(i+1,distance_list[i]['point'],distance_list[i]['distance']))

###老师的解答

A = [(1.33, 2.1), (1.2, 2.63), (1.77, 2.8), (1.1, 2.1), (1.4, 2.3), (1.6, 2.53), (1.13, 3.07), (2.5, 2.87), (2.2, 2.13),
     (1.6, 1.77), (1.8, 2.13), (2.07, 2.43), (2.0, 2.8), (1.63, 3.07), (1.47, 2.9), (1.73, 3.2), (2.37, 3.07),
     (2.5, 2.13), (2.33, 2.57), (1.5, 2.47), (1.87, 2.4), (2.0, 3.03), (2.43, 2.57)]
B = [(1.27, 0.87), (1.77, 1.13), (2.77, 0.43), (1.93, 0.23), (1.7, 0.63), (2.3, 0.97), (2.4, 1.13), (2.5, 0.7),
     (2.07, 1.23), (2.6, 1.37), (1.0, 1.07), (1.5, 0.3), (1.77, 0.7), (1.63, 0.87), (2.2, 0.73), (2.33, 0.37),
     (1.97, 1.13), (2.13, 0.63), (2.07, 0.37), (2.03, 0.87), (1.97, 0.83), (1.6, 0.87), (1.53, 1.1), (1.5, 1.13),
     (1.5, 1.13), (2.17, 1.1), (2.27, 1.2), (2.3, 1.2), (2.83, 0.7), (2.97, 1.1), (2.8, 1.1), (2.8, 0.8)]
C = [(3.73, 2.7), (4.4, 2.73), (4.87, 1.53), (4.33, 1.7), (3.97, 2.27), (3.73, 2.57), (4.37, 2.67), (4.6, 2.1),
     (3.9, 2.6), (3.93, 2.63), (3.93, 2.63), (4.8, 2.3), (4.6, 2.43), (4.23, 2.53), (4.17, 2.23), (4.37, 2.3),
     (4.4, 2.47), (3.97, 2.17), (3.63, 1.87), (3.5, 2.23), (3.77, 2.43), (3.9, 1.7), (3.67, 1.5), (3.5, 1.57),
     (4.13, 1.3), (4.47, 1.23), (4.7, 1.47), (4.9, 1.77), (4.6, 1.9), (4.53, 1.5), (4.17, 1.43), (4.17, 1.87),
     (4.43, 1.93), (3.87, 1.93), (3.8, 2.13)]

import math
data = []

for points,lable in ((A,'A'),(B,'B'),(C,'C')):
    for point_x,point_y in points:
        data.append((point_x,point_y,lable))

def distance(point1, point2):
    sx = math.pow((point1[0]-point2[0]),2)
    sy = math.pow((point1[1] - point2[1]), 2)
    return math.sqrt(sx+sy)
distances = []
def knn(data, point, k):
    lables = {}
    for point_x,point_y,lable in data:
        if lable not in lables:
            lables[lable] = 0
        dis = distance((point_x,point_y),point)
        distances.append((dis,(point_x,point_y,lable)))
    max_lable = None
    for _,(x,y,lable) in sorted(distances,key= lambda e:e[0])[:k]:
        if max_lable is None:
            max_lable=(lable, lables[lable])
        lables[lable]+=1
        if lables[lable] > max_lable[1]:
            max_lable = (lable,lables[lable])
    print(lables,max_lable)
    return max_lable[0]

print(knn(data, (2.9, 1.77), 20))